template< class T >
inline T two( T var ){
    return var*var ;
}
inline Int fastPow(Int x, Int y) {
    Int res= (Int)1;
    for ( ; y ; ) {
        if ( (y&1) ) {
            res*= x;
        }
        x*=x;
        y>>=1;
    }
    return res;
}
template< class T1, class T2 >
inline T2 MOD( T1 x , T2 b ){
    return (x%b);
}
template< class T >
inline T gcd(T a, T b){
    // NEGATIVE VALUE'R GCD HOTE PARBE NA
    assert( (a >=0 && b>=0 ) );
    while( b > T(0) ){
        a%=b;
        swap(a,b);
    }
return a;
}

inline int toI(string _str){
    // STRING EMPTY HOTE PARBE NA
    assert( LN(_str) );
    int var;
    sscanf(_str.c_str(),"%d",&var);
return var;
}
inline string toS(int var){
    char _buff[50];
    sprintf( _buff,"%d",var);
return (string)_buff;
}


struct Triple {
    Int d;
    Int x;
    Int y;
    Triple(Int d, Int x, Int y):
            d(d),x(x),y(y) {
        ;
    }
};
Triple egcd(Int a, Int b) {
    if (!b)return Triple(a,1,0);
    Triple q=egcd(b,a%b);
    return Triple(q.d, q.y, q.x-a/b*q.y);
}
inline Int invmod(Int a, Int n) {
    Triple t=egcd(a,n);
    if (t.d>1)return 0;
    Int r=t.x%n;
    return (r<0?r+n:r);
}
const int mod=(int)1e9+7;
const int maxn=1010;
Int im[maxn]; //inverse mod
Int fact[maxn];
inline void findFactorials(int upto) {
    fact[0]=fact[1]=im[1]=1;
    for (int i=2;i<=upto;++i) {
        im[i]=invmod(i,mod);
        fact[i]=(fact[i-1]*i)%mod;
    }
}
Int C[maxn][maxn];
// find NcR
Int ncr(Int a, Int b) {
    int LM=min(b,a-b);
    if (C[a][LM])return C[a][LM];
    C[a][0]=1LL;
    int LIM=(a+3)>>1;
    for (int U=a,D=1; D<LIM; ++D,--U) {
        C[a][D]=(((C[a][D-1] * U)%mod) * im[D])% mod;
    }
    return C[a][LM];
}
// another NcR formula
Int ncr(Int n, Int r){
    return (fact[n]*invmod(fact[r],mod)*invmod(fact[n-r],mod))%mod;
}

inline void preprocess() {
    findFactorials(1000);
    SET(C,0);
}

Int fib[maxn+5];
inline void Fibonacci(int upto) {
    fib[0]=0;
    fib[1]=1;
    fib[2]=1;
    for (int i=3;i<=upto;++i) {
        fib[i]=fib[i-1]+fib[i-2];
    }
}

/*
 * http://goo.gl/8tUaQ
 * Zeckendorf(n)= {
 * local(k); a=0;
 * while(n>0, k=0;
 * 	while(fibonacci(k)<=n, k=k+1);
 * 	a=a+10^(k-3); n=n-fibonacci(k-1); ); a
 * }
 *
 * { for (n=0, 10000, Zeckendorf(n); print(n, " ", a);
 */

int res[50];
int leftmost;
inline void Zeckendorf(int n) {
    int k;
    SET(res,0);

    leftmost=-1;
    while (n>0) {
        k=0;
        while (fib[k]<=n) {
            k=k+1;
        }
        res[k-3]=1;
        n=n-fib[k-1];
        if (leftmost==-1)leftmost=k-3;
    }
    for (int i=leftmost;i>=0;--i)
        putchar(res[i]?'1':'0');
    line;

}
int tot;
vector< pair<Int,int> > primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (int i=0; i<cnt&&primes[i]*primes[i]<=number;++i) {
        if ( (number%primes[i]) ==0) {
            int power=0;
            while ((number%primes[i])==0) {
                number/=primes[i];
                ++power;
            }
            primeDivisors.pb(mk(primes[i],power));
        }
    }
    if ( number!=1) {
        primeDivisors.pb(mk(number,1));
    }
    tot=SZ(primeDivisors);
}

vector< pair<Int,int> >primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (Int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            int power = 0;
            do {
                power++;
                number /= i;
            } while (number % i == 0);
            primeDivisors.pb(mk(i, power));
        }
    }
    if (number != 1)
        primeDivisors.pb(mk(number, 1));
}
vector<int> divisors;
void genDivisor(int at, int current) {
    if (at==SZ(primeDivisors)) {
        divisors.pb(current);
        return ;
    }
    int p=primeDivisors[at].first;
    int power=primeDivisors[at].second;
    for (int i=0;i<=power;++i) {
        genDivisor(at+1,current);
        current*=p;
    }
}
inline void getDivisor(int N) {
    factorize(N);
    divisors.clear();
    genDivisor(0,1);
    cout<<N<<" = ";
    fo(i,SZ(divisors)){
      cout<<divisors[i]<<' ';
    }
    line;
}

const int inf = (int)100000;
bitset<inf> used;
int primes[inf];
int cnt;

inline void sieve() {
    int sqrtN = (int)sqrt((double)inf)+1;
    used=0;
    int i,j;
    for (i=3;i<=sqrtN;i+=2) {
        if (!used[i]) {
            for (j=i*i;j<inf;j+=i) {
                used[j]=1;
            }
        }
    }
    cnt=0;
    primes[cnt++]=2;
    for (i=3;i<inf;i+=2) {
        if (!used[i])primes[cnt++]=i;
    }
}
inline Int getNext(int num, int prime) {
    Int v=ceil( ((double)num)/prime );
    v=v*prime;
    if (v==prime)v+=prime;
    return v;
}
inline void segmentSieve(int a, int b) {
    used=0;
    int i;
    int upto= (int)sqrt(double(b))+1;
    for (i=0; i<cnt&&primes[i]<=upto;++i) {
        for (Int j=getNext(a,primes[i]);j<=b;j+=primes[i]) {
            used[j-a]=1;
        }
    }
    int cnt=0;
    for (Int i=lo;i<=hi;++i) {
        if (i!=1&&!used[ (int)i-lo]) {
            ++cnt;
        }
    }
    cout<<cnt;
}
inline Int Divisors(Int num) {
    // return number of divisors of a number "num"
    // need sieve() function to call first
    Int res=1;
    for (Int i=0; i<cnt&&(primes[i]*primes[i])<=num; ++i) {
        if ( num%primes[i] ==0 ) {
            int power=0;
            do {
                num/=primes[i];
                ++power;
            } while (num%primes[i] ==0 );
            res*=(power+1);
        }
    }
    if (num!=1) {
        res*=(2);
    }
    return res;
}